#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

class NumberLabyrinthDiv2 {
public:
	int getMinimumNumberOfMoves(vector <string>, int, int, int, int, int);
	bool checkBound(int x, int y);
	int grid[51][51][51];
	int M;
	int N;
};

int NumberLabyrinthDiv2::getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) {
	M = board.size();
	N = board[0].size();
	memset(grid, -1, sizeof(grid));

	deque<pair<pair<int, int>, int> > q;
	q.push_back(make_pair(make_pair(r1, c1), K));
	grid[r1][c1][K] = 0;
	while(!q.empty()){
		int x = q.front().first.first;
		int y = q.front().first.second;
		int k = q.front().second;
		q.pop_front();
		if(r2 == x && c2 == y) continue;
		if(board[x][y] == '.' ){
			if(k>0)
				for(int i=0; i<4; i++){
					for(int j=1; j<=9; j++){
						int xx = x + dx[i] * j;
						int yy = y + dy[i] * j;
						if(checkBound(xx, yy) && grid[xx][yy][k-1] == -1){
							grid[xx][yy][k-1] = grid[x][y][k] + 1; //j;
							q.push_back(make_pair(make_pair(xx, yy), k-1));
						}
					}
				}
		}
		else{
			int j = board[x][y] - '0';
			if(j > 0)
				for(int i=0; i<4; i++){
					int xx = x + dx[i] * j;
					int yy = y + dy[i] * j;
					if(checkBound(xx, yy) && grid[xx][yy][k] == -1){
						grid[xx][yy][k] = grid[x][y][k] + 1; //(board[x][y] - '0');
						q.push_back(make_pair(make_pair(xx, yy), k));
					}
				}
		}
	}
	int ret = -1;
	for(int i=0; i<=K; i++){
		if( grid[r2][c2][i]!=-1){
			if(ret == -1 || grid[r2][c2][i] < ret){
				ret = grid[r2][c2][i];
			}
		}
	}
	return ret;
}

bool NumberLabyrinthDiv2::checkBound(int x, int y){
	return x>=0 && x<M && y>=0 && y<N;
}


double test0() {
	string t0[] = {"...2",
 "....",
 "3..."};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int p1 = 0;
	int p2 = 0;
	int p3 = 2;
	int p4 = 3;
	int p5 = 0;
	NumberLabyrinthDiv2 * obj = new NumberLabyrinthDiv2();
	clock_t start = clock();
	int my_answer = obj->getMinimumNumberOfMoves(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = -1;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	string t0[] = {"...2",
 "....",
 "3..."};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int p1 = 0;
	int p2 = 0;
	int p3 = 2;
	int p4 = 3;
	int p5 = 1;
	NumberLabyrinthDiv2 * obj = new NumberLabyrinthDiv2();
	clock_t start = clock();
	int my_answer = obj->getMinimumNumberOfMoves(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 2;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	string t0[] = {"...3",
 "....",
 "2..."};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int p1 = 0;
	int p2 = 0;
	int p3 = 2;
	int p4 = 3;
	int p5 = 3;
	NumberLabyrinthDiv2 * obj = new NumberLabyrinthDiv2();
	clock_t start = clock();
	int my_answer = obj->getMinimumNumberOfMoves(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 3;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test3() {
	string t0[] = {"55255",
 ".0.0.",
 "..9..",
 "..3..",
 "3.9.3",
 "44.44"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int p1 = 3;
	int p2 = 2;
	int p3 = 4;
	int p4 = 2;
	int p5 = 10;
	NumberLabyrinthDiv2 * obj = new NumberLabyrinthDiv2();
	clock_t start = clock();
	int my_answer = obj->getMinimumNumberOfMoves(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 6;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test4() {
	string t0[] = {"920909949",
 "900020000",
 "009019039",
 "190299149",
 "999990319",
 "940229120",
 "000409399",
 "999119320",
 "009939999"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	int p1 = 7;
	int p2 = 3;
	int p3 = 1;
	int p4 = 1;
	int p5 = 50;
	NumberLabyrinthDiv2 * obj = new NumberLabyrinthDiv2();
	clock_t start = clock();
	int my_answer = obj->getMinimumNumberOfMoves(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 10;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	time = test3();
	if (time < 0)
		errors = true;
	
	time = test4();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
